home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 201-220 / scopedisk216 / smartdisk / smartdisk.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-20  |  14.7 KB  |  594 lines
  1. /*
  2.  * SmartDisk 1.3.
  3.  *
  4.  * Created by David Le Blanc 29/10/91 Absolutely no copywrite. But if you improve
  5.  * it, please send me a new version (with source!) 
  6.  * 
  7.  * Current limitations.
  8.  *   No command line options, device and cache size are hard-wired into the program.
  9.  *   Only one unit is supported.
  10.  *
  11.  * Obvious enhacements.
  12.  *   Make device and unit configurable, as well as cache size and shape.
  13.  *
  14.  * Some performance quotes: (Doesn't everyone make these??)
  15.  * Background:  I have a directory called MAN: which has 355 manuals.
  16.  *
  17.  * WARNING: These are bad examples, since a 'dir' reads the disk, then sorts the
  18.  * contents, then writes the data to the screen. These times include the sorting
  19.  * and output of the directory. This sorting and output time is in the order
  20.  * of 1.5 to 2 seconds.
  21.  *
  22.  * Normal DIR MAN:        12 seconds
  23.  * Cache enabled but empty      9  seconds (prefetch does work!) 
  24.  * Cache primed                 5  seconds.
  25.  *
  26.  * With a slower drive and/or faster machine these times can only improve.
  27.  * I have a drive capable of 800k/sec on my unaccelerated A500. Those with
  28.  * a 150K/sec A590 would notice a greater performance boost. Same for those
  29.  * with 'bloody fast machines' (grumble :) If I was REALLY worried about making
  30.  * the statistic look good, then I'd test it on an A590.
  31.  *
  32.  * A590 USERS: You MUST edit the 'scsi.device' to 'xt.device' or it will NOT WORK.
  33.  * GVP  USERS: You MUST edit the 'scsi.device' to 'gvpscsi.device' or it will
  34.  *             NOT WORK.
  35.  *
  36.  * SmartDisk: A SCSI.DEVICE disk cache.
  37.  *
  38.  * 1.3:        Added Prefetch and fixed 'CMD_WRITE' to update instead of
  39.  *              flush cache entry.
  40.  * 1.2:         Added many optimisation such as moving the semaphore locks to
  41.  *              the update functions, and for a request of many blocks, the
  42.  *              blocks are read in all at once into the users buffer, THEN
  43.  *              copied to cache. (Instead of read into cache one at a time and
  44.  *              then copied to the user buffer)
  45.  * 1.1:        Found a major problem. The following union under Lattice 5.10a
  46.  *              generates unexpected (probably correct) code. The key, line and
  47.  *        offset fields are actually unioned together, whereas I though
  48.  *        the union would be between the two int declarations. 
  49.  *
  50.  *              union sector {
  51.  *                 int key:32-LINE_BITS-ITEM_BITS,
  52.  *                     line:LINE_BITS,
  53.  *                     offset:ITEM_BITS ;
  54.  *                 int sector ;
  55.  *                 } ;
  56.  *
  57.  *        I made the bit fields a separate structure, and union'ed the 
  58.  *          sector and the new structure together.
  59.  *
  60.  * 1.0:        My school assigment was to write a N-way set associative cache
  61.  *        simulator and to plot hit-rate percentages. With a bit of
  62.  *        work, it is not a Hard Disk cache! Vive la Amiga!
  63.  *
  64.  *
  65.  * History:
  66.  *    29/10/91 : Sat down an wrote a cache.
  67.  *    30/10/91 : Problem? Works Great Now.
  68.  *    31/10/91 : Fixed up the 'aging' of blocks to handle the
  69.  *             : counter wrapping after 2^32 buffer creates/updates.
  70.  *             : (How long does 2^32 DIFFERENT accesses take?? With a fast hard
  71.  *                disk going continually, I estimate about two months.)
  72.  *             : Cleaned up the code a tad.
  73.  */
  74.  
  75. struct IOStdReq *IO;        /* All IO goes through here now. */
  76. struct SignalSemaphore *ss ;    /* To force single threading     */
  77.                 /* through the code responsible     */
  78.                 /* for updating the cache     */
  79. ULONG counter ;
  80.  
  81. int allocnum = 0 ;
  82.  
  83. void printf(char *fmt, ...) ;
  84.  
  85. /*
  86.  * Constants. Adjust for adjusting cache size and shape.
  87.  */
  88.  
  89. #define ITEM_SIZE 512           /* No change - sector size */
  90.  
  91. #define LINE_SIZE   4           /* Increase for prefetch */
  92. #define SETS        8           /* N-way set associative */
  93. #define LINES      32           /* N lines of cache      */
  94.  
  95. /*
  96.  * Bit fields. Adjust to match above constants.
  97.  */
  98.  
  99. #define ITEM_BITS  2            /* 2^ITEM_BITS = LINE_SIZE */
  100. #define LINE_BITS  5            /* 2^LINE_BITS = LINES     */
  101.  
  102. struct bitaddress {
  103.    int key:32-LINE_BITS-ITEM_BITS,
  104.        line:LINE_BITS,
  105.        offset:ITEM_BITS ;
  106.    } ;
  107.  
  108. union sector {
  109.    int sector ;
  110.    struct bitaddress s ;
  111.    } ;
  112.  
  113. struct cache_line {
  114.    int key ;                     /* Item key */
  115.    int age ;                     /* AGE for LRU alg */
  116.    int valid ;
  117.    char *buffer ;                /* [LINE_SIZE][ITEM_SIZE] of DATA */
  118.    } ;
  119.  
  120. struct cache_line cache[SETS][LINES] ;
  121.  
  122. /*
  123.  * A buffer for scsidisk.device to go through.
  124.  */
  125. char __chip globbuffer[LINE_SIZE << 9] ;
  126.  
  127. #define DEV_BEGINIO (-30)
  128. #define DEV_ABORTIO (-36)
  129.  
  130. void (*__asm oldbeginio)(register __a1 struct IOStdReq *,
  131.                          register __a6 struct Device *dev) ;
  132. /*
  133.  * Scan for sector, and return the set it resides in.
  134.  */
  135. int
  136. FindEntry(union sector *s) {
  137.  
  138.    int set ;
  139.  
  140.    for (set = 0; set < SETS; set++) 
  141.       if (cache[set][s->s.line].valid) {
  142.          if (cache[set][s->s.line].key == s->s.key) {
  143.             cache[set][s->s.line].age = counter ++ ;
  144.             return set ;
  145.             }
  146.          }
  147.       else
  148.          break ;
  149.  
  150.    return -1 ;
  151.    }
  152.  
  153. /*
  154.  * Pick a set from the associated cache, and return
  155.  * the set number. The cache memory is also allocated
  156.  * before returning. The cache entry is marked VALID. so if you
  157.  * can't fill it, remember to clear it!
  158.  */
  159. int
  160. AllocCache(union sector *s) {
  161.    int set ;
  162.    int oldest ;
  163.    int oldset ;
  164.    int found ;
  165.    int age ;
  166.  
  167.    oldset = 0 ;
  168.    oldest = 0 ;
  169.    found  = 0 ;
  170.  
  171.    for (set = 0; set < SETS; set++) 
  172.       if (cache[set][s->s.line].valid) {
  173.          if (cache[set][s->s.line].key != s->s.key) {
  174.             /*
  175.              * This 'age' calculation is complicated since normally, 
  176.              * AGE = COUNTER - CACHE.AGE, however, if counter has
  177.              * wrapped to zero, such evaluation evaluates ages of < 0 and
  178.              * these entries will never be reselected for reuse.
  179.              *
  180.              * If counter wraps to zero, then CACHE.AGE is generally larger
  181.              * than COUNTER, so we evaluate age as the total of MAXINT-AGE 
  182.              * plus the current value of the counter. IE, how much it took to
  183.              * wrap and reach the current position.
  184.              *
  185.              * Hence, 
  186.              * AGE = ~0 - CACHE.AGE + COUNTER
  187.              */
  188.             age = cache[set][s->s.line].age ;
  189.             if (age > counter)
  190.                age = ((ULONG) ~0 - age) + counter ;
  191.             else
  192.                age = counter - age ;
  193.  
  194.             if (age > oldest)
  195.                oldest = age, oldset = set ;
  196.             }
  197.          else {
  198.             found = 1 ;
  199.             break ; /* key = s.key. Line already in cache */
  200.             }
  201.          }
  202.       else
  203.          break ; /* !valid. Found a free line */
  204.  
  205.    if (found) {
  206.       return -1 ;
  207.       }
  208.  
  209.    if (set == SETS)
  210.       set = oldset ;
  211.  
  212.    cache[set][s->s.line].age = counter ++ ;
  213.    cache[set][s->s.line].key = s->s.key ;
  214.  
  215.    /*
  216.     * If no buffer, allocate one.
  217.     */
  218.    if (! cache[set][s->s.line].buffer )
  219.       cache[set][s->s.line].buffer = AllocMem(LINE_SIZE << 9, MEMF_PUBLIC) ;
  220.  
  221.    /*
  222.     * If STILL no buffer, return failure. Otherwise set the VALID flag.
  223.     */
  224.    if (cache[set][s->s.line].buffer ) {
  225.       cache[set][s->s.line].valid = 1 ;
  226.       allocnum ++ ;
  227.       }
  228.    else {
  229.       cache[set][s->s.line].valid = 0 ;         /* Allocation failed */
  230.       return -1 ;
  231.       }
  232.  
  233.    return set ;
  234.    }
  235.  
  236. /*
  237.  * Allocate a line of cache and read it from disk.
  238.  */
  239. int
  240. ReadCache(union sector *s) {
  241.    struct MsgPort *port ;
  242.    char *dest ;
  243.    int  set ;
  244.  
  245.    ObtainSemaphore(ss);
  246.  
  247.    port = CreateMsgPort() ;
  248.  
  249.    if (!port) {
  250.       ReleaseSemaphore(ss) ;
  251.       return -1 ;
  252.       }
  253.  
  254.    if (s->s.offset)
  255.       s->s.offset = 0 ;
  256.  
  257.    IO->io_Message.mn_ReplyPort = port ;
  258.  
  259.    IO->io_Command = CMD_READ;
  260.    IO->io_Offset = s->sector << 9 ;
  261.    IO->io_Length = LINE_SIZE << 9 ;
  262.    IO->io_Data = (APTR) globbuffer ;
  263.  
  264.    oldbeginio(IO,IO->io_Device) ;
  265.    WaitIO(IO) ;
  266.  
  267.    DeleteMsgPort(port) ;
  268.  
  269.    if (IO->io_Error) {
  270.       ReleaseSemaphore(ss) ;
  271.       return -1 ;
  272.       }
  273.  
  274.    set = AllocCache(s) ;
  275.  
  276.    if (set < 0) {
  277.       ReleaseSemaphore(ss) ;
  278.       return -1 ;
  279.       }
  280.  
  281.    dest = cache[set][s->s.line].buffer ;
  282.  
  283.    CopyMemQuick(globbuffer, dest, LINE_SIZE << 9) ;
  284.  
  285.    ReleaseSemaphore(ss) ;
  286.    return 0 ;
  287.    }
  288.  
  289. int
  290. ReadBufferToCache(int linestart,int unread,char *buffer) {
  291.  
  292.    union sector s ;
  293.    struct MsgPort *port ;
  294.    int set ;
  295.  
  296.    ObtainSemaphore(ss);
  297.    s.sector = linestart ;
  298.  
  299.    port = CreateMsgPort() ;
  300.  
  301.    if (!port) {
  302.       ReleaseSemaphore(ss) ;
  303.       return -1 ;
  304.       }
  305.  
  306.    IO->io_Message.mn_ReplyPort = port ;
  307.  
  308.    /*
  309.     * Read enough to fill the buffer.
  310.     */
  311.  
  312.    IO->io_Command = CMD_READ;
  313.    IO->io_Offset = linestart << 9 ;
  314.    IO->io_Length = unread << 9 ;
  315.    IO->io_Data = (APTR) buffer ;
  316.  
  317.    oldbeginio(IO,IO->io_Device) ;
  318.    WaitIO(IO) ;
  319.  
  320.    DeleteMsgPort(port) ;
  321.  
  322.    if (IO->io_Error) {
  323.       ReleaseSemaphore(ss) ;
  324.       return -1 ;
  325.       }
  326.  
  327.    while (unread) {
  328.       set = AllocCache(&s) ;
  329.       if (set < 0) {
  330.          ReleaseSemaphore(ss) ;
  331.          return -1 ;
  332.          }
  333.       else {
  334.          CopyMemQuick(buffer,cache[set][s.s.line].buffer, LINE_SIZE << 9) ;
  335.          }
  336.  
  337.       s.sector += LINE_SIZE ;
  338.       unread -= LINE_SIZE ;
  339.       buffer += (LINE_SIZE << 9) ;
  340.       }
  341.  
  342.    ReleaseSemaphore(ss) ;
  343.    return 0 ;
  344.    }
  345.  
  346. /* 
  347.  * This functions checks the cache. If the sector is there, it returns
  348.  * the buffer, otherwise it returns NULL.
  349.  */
  350. char *
  351. FindCache(union sector *s,int set) {
  352.    return & (cache[set][s->s.line].buffer[s->s.offset << 9 ] ) ;
  353.    }
  354.  
  355. /*
  356.  * This function takes 'sector' and set, and decides if the next sector
  357.  * is in the cache.
  358.  */
  359. int
  360. NextEntry(union sector *s, int set) {
  361.    int line ;
  362.  
  363.    line = s->s.line ;
  364.    s->sector ++ ;
  365.  
  366.    if (line == s->s.line) {
  367.       return set ;
  368.       }
  369.    else
  370.       return FindEntry(s) ;
  371.    }
  372.  
  373. /*
  374.  * Search for sector, and mark it invalid.
  375.  */
  376. void
  377. ClearEntry(union sector *s,int set) {
  378.    cache[set][s->s.line].valid = 0 ;
  379.    }
  380.  
  381. CacheUpdate(union sector *s, int seccount, char *buffer) {
  382.    int set ;
  383.  
  384.    ObtainSemaphore(ss) ;
  385.  
  386.    while (seccount) {
  387.       set = FindEntry(s) ;
  388.       if (set >= 0) {
  389.          CopyMemQuick(buffer,FindCache(s,set), ITEM_SIZE) ;
  390.          cache[set][s->s.line].age = counter ++ ;
  391.          }
  392.  
  393.       buffer += ( ITEM_SIZE ) ;
  394.       seccount -- ;
  395.       s->sector ++ ;
  396.       }
  397.  
  398.    ReleaseSemaphore(ss) ;
  399.    return 0 ;
  400.    }
  401.  
  402. void __saveds __asm mybeginio(register __a1 struct IOStdReq *req,
  403.                               register __a6 struct Device *dev) {
  404.  
  405.    union sector s ;
  406.    int   set ;
  407.    int   command ;
  408.    int   secnum ;
  409.    char  *source ;
  410.    char  *buffer ;
  411.  
  412.    int   unread ;
  413.    int   linestart ;
  414.  
  415.    s.sector = req->io_Offset >> 9 ;
  416.    secnum   = req->io_Length >> 9 ;
  417.    command  = req->io_Command ;
  418.    buffer   = (char *) req->io_Data ;
  419.  
  420.    if (command == CMD_WRITE)
  421.       CacheUpdate(&s,secnum,buffer) ;
  422.  
  423.    if (command == CMD_READ) {
  424.  
  425.       while (secnum) {
  426.          set = FindEntry(&s) ;
  427.  
  428.          if (set < 0) {
  429.             source = NULL ;
  430.             }
  431.          else {
  432.             source = FindCache(&s,set) ;
  433.             }
  434.  
  435.          /*
  436.           * Scan copying buffers to the request.
  437.           */
  438.  
  439.          while (secnum && source) {
  440.             CopyMemQuick(source,buffer,ITEM_SIZE) ;
  441.             buffer += ITEM_SIZE ;
  442.  
  443.             secnum -- ;
  444.             if (secnum) {
  445.                set = NextEntry(&s, set) ;
  446.                if (set < 0) {
  447.                   source = NULL ;
  448.                   }
  449.                else {
  450.                   source = FindCache(&s,set) ;
  451.                   }
  452.                }
  453.             }
  454.  
  455.          if (!secnum) {                                 /* Done ? */
  456.             break ;
  457.             }
  458.  
  459.          /*
  460.           * If we are in the middle of a line, read it in.
  461.           */
  462.          if (s.s.offset) {
  463.             int original = s.sector ;
  464.  
  465.             s.s.offset = 0 ;
  466.             if (ReadCache(&s) < 0) {
  467.                }
  468.  
  469.             s.sector = original ;
  470.             }
  471.          else {
  472.             /*
  473.              * Start scanning at next line.
  474.              */
  475.             unread = 0 ;
  476.  
  477.             linestart = s.sector ; 
  478.  
  479.             /*
  480.              * Scan counting sectors that need reading.
  481.              */
  482.             while ((secnum>unread) && (set < 0)) {
  483.                s.sector = linestart + unread ;
  484.                set = FindEntry(&s) ;
  485.                /*
  486.                 * For efficiency, if a sector is not found, advance to
  487.                 * the next line instead of the next sector.
  488.                 */
  489.                if (set < 0) {
  490.                   unread += LINE_SIZE ;
  491.                   }
  492.                }
  493.  
  494.             if (unread > secnum) {
  495.                unread -= LINE_SIZE ;
  496.                }
  497.  
  498.             if (unread) {
  499.                /*
  500.                 * Read the cache into the supplied buffer, and copy
  501.                 * it to cache memory.
  502.                 */
  503.                ReadBufferToCache(linestart,unread,buffer) ;
  504.                buffer += ( unread << 9 ) ;
  505.                }
  506.              else {
  507.                /*
  508.                 * If there are more sectors, call 'ReadCache()' to get them.
  509.                 */
  510.                ReadCache( (union sector *)&linestart) ;
  511.                }
  512.  
  513.             /*
  514.              * Pick up where we left off.
  515.              */
  516.             s.sector = linestart + unread ;
  517.             secnum -= unread ;
  518.             if (secnum < 0)
  519.                break ;
  520.             }
  521.          }
  522.       /*
  523.        * Done!!!
  524.        */
  525.       }
  526.  
  527.    if (command != CMD_READ)
  528.       oldbeginio(req,dev) ;
  529.    else {
  530.       req->io_Actual = req->io_Length ;
  531.       ReplyMsg((struct Message *) req) ;
  532.       } ;
  533.  
  534.    }
  535.  
  536. int
  537. main(int argc, char *argv[]) {
  538.  
  539.    int error ;
  540.    int line,set ;
  541.    int devopen ;    
  542.    struct MsgPort  *port ;
  543.  
  544.    port = CreateMsgPort() ;
  545.    IO = CreateIORequest(port,sizeof(struct IOStdReq)) ;
  546.  
  547.    error = OpenDevice("scsi.device",0,(struct IORequest *)IO, 0) ;
  548.  
  549.    if (error)
  550.       goto fail ;
  551.    else
  552.       devopen = 1 ;
  553.  
  554.    ss = AllocMem(sizeof(struct SignalSemaphore), MEMF_PUBLIC) ;
  555.  
  556.    if (!ss)
  557.       goto fail ;
  558.  
  559.    SumLibrary( (struct Library *) IO->io_Device) ; 
  560.  
  561.    InitSemaphore(ss) ;
  562.  
  563.    oldbeginio = SetFunction((struct Library *)IO->io_Device,DEV_BEGINIO,(APTR)mybeginio) ;
  564.    Wait (SIGBREAKF_CTRL_F) ;
  565.  
  566.    ObtainSemaphore(ss) ;
  567.    SetFunction((struct Library *)IO->io_Device,DEV_BEGINIO,(APTR)oldbeginio) ;
  568.    ReleaseSemaphore(ss) ;
  569.  
  570.    for (line = 0; line < LINES; line ++)
  571.       for (set = 0; set < SETS; set ++)
  572.          if (cache[set][line].buffer) {
  573.             FreeMem( cache[set][line].buffer,LINE_SIZE << 9 ) ;
  574.             allocnum -- ;
  575.             }
  576.  
  577.    if (allocnum)
  578.       printf("Allocation mismatch. %d buffers left lying around\n",allocnum) ;
  579.  
  580. fail:
  581.    if (ss)
  582.       FreeMem(ss,sizeof(struct SignalSemaphore)) ;
  583.    if (devopen) {
  584.       IO->io_Message.mn_ReplyPort = port ;
  585.       CloseDevice((struct IORequest *)IO) ;
  586.       }
  587.    if (IO)
  588.       DeleteIORequest((struct IORequest *)IO) ;
  589.    if (port)
  590.       DeleteMsgPort(port) ;
  591.  
  592.    return 0 ;
  593.    }
  594.